There are a variety of different data structures a programmer can utilize to store data in a computer system. In storing data used for search engines, it is common to utilize an inverted index data structure. An inverted index is an index that stores a listing of which documents/results contain particular words or terms. Part of the process of creating an inverted index is to create a forward index. A forward index is an index that stores a list of words or terms contained in each document. The forward index can then be sorted to transform it into an inverted index.
Generating and maintaining a large-scale search engine index represents a significant storage and processing challenge. It is common to utilize compression to reduce the size of the various indexes, including the search forward index. Traditionally, however, the compression used has either been optimized for speed/performance, or optimized for size. For a search forward index, however, it is desirable to have both.